51. N-Queens.go

package leetcode

// 解法一 DFS
funcsolveNQueens(nint) [][]string {
col, dia1, dia2, row, res:=make([]bool, n), make([]bool, 2*n-1), make([]bool, 2*n-1), []int{}, [][]string{}
putQueen(n, 0, &col, &dia1, &dia2, &row, &res)
returnres
}

// 尝试在一个n皇后问题中, 摆放第index行的皇后位置
funcputQueen(n, indexint, col, dia1, dia2*[]bool, row*[]int, res*[][]string) {
ifindex==n {
*res=append(*res, generateBoard(n, row))
return
 }
fori:=0; i<n; i++ {
// 尝试将第index行的皇后摆放在第i列
if!(*col)[i] &&!(*dia1)[index+i] &&!(*dia2)[index-i+n-1] {
*row=append(*row, i)
 (*col)[i] =true
 (*dia1)[index+i] =true
 (*dia2)[index-i+n-1] =true
putQueen(n, index+1, col, dia1, dia2, row, res)
 (*col)[i] =false
 (*dia1)[index+i] =false
 (*dia2)[index-i+n-1] =false
*row= (*row)[:len(*row)-1]
 }
 }
return
}

funcgenerateBoard(nint, row*[]int) []string {
board:= []string{}
res:=""
fori:=0; i<n; i++ {
res+="."
 }
fori:=0; i<n; i++ {
board=append(board, res)
 }
fori:=0; i<n; i++ {
tmp:= []byte(board[i])
tmp[(*row)[i]] ='Q'
board[i] =string(tmp)
 }
returnboard
}

// 解法二 二进制操作法 Signed-off-by: Hanlin Shi shihanlin9@gmail.com
funcsolveNQueens2(nint) (res [][]string) {
placements:=make([]string, n)
fori:=rangeplacements {
buf:=make([]byte, n)
forj:=rangeplacements {
ifi==j {
buf[j] ='Q'
 } else {
buf[j] ='.'
 }
 }
placements[i] =string(buf)
 }
varconstructfunc(prev []int)
construct=func(prev []int) {
iflen(prev) ==n {
plan:=make([]string, n)
fori:=0; i<n; i++ {
plan[i] =placements[prev[i]]
 }
res=append(res, plan)
return
 }
occupied:=0
fori:=rangeprev {
dist:=len(prev) -i
bit:=1<<prev[i]
occupied|=bit|bit<<dist|bit>>dist
 }
prev=append(prev, -1)
fori:=0; i<n; i++ {
if (occupied>>i)&1!=0 {
continue
 }
prev[len(prev)-1] =i
construct(prev)
 }
 }
construct(make([]int, 0, n))
return
}